package com.algorithm.code.tree;

import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.Deque;
import java.util.Queue;

/**
 * @description 二叉查找树
 * 1. 节点:左大右小
 * 2. 树的遍历：参考https://www.jianshu.com/p/1bfeedd54eaa
 * @program: sudy
 * @author: kukuxiahuni
 * @create: 2020-01-24 14:57
 **/
public class BinarySearchTree<T> {
    /**
     * 根节点
     */
    private TreeNode<T> root = null;
    private final Comparator<? super T> comparator;

    public BinarySearchTree(Comparator<? super T> comparator) {
        this.comparator = comparator;
    }

    /**
     * 默认构造函数
     */
    public BinarySearchTree() {
        this.comparator = null;
    }

    /**
     * @Description: 前序遍历
     * @Param:
     * @return:
     * @Author: kukuxiahuni
     * @Date: 2020/1/30
     */
    public void preOrder(TreeNode root) {

        if (root == null) {
            return;
        }
        System.out.println(root.value);
        preOrder(root.left);
        preOrder(root.right);
    }


/**
 *
 */
    /**
     * 中左右
     * 迭代方式的前序遍历
    * @param root:
    * @return:
    * @author: kukuxiahuni
    * @create: 2020/2/3 20:09
    * @modify_author: kukuxiahuni
    * @modify_time: 2020/2/3 20:09
    */
    public void preOrderWithIterator(TreeNode root) {
        if (root == null) {
            return ;
        }

        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {

            TreeNode node = stack.pop();
            System.out.println(node.value);

            if (node.right != null) {
                stack.push(node.right);
            }

            if (node.left != null) {
                stack.push(node.left);
            }

        }
    }

    public final void preOrderWithIterator2(TreeNode root) {
        if (root == null) {
            return;
        }

        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {

            if (cur != null) {
                System.out.println(cur.value);
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode node = stack.pop();
                cur = node.right;
            }
        }


    }

    /**
     * @Description: 中序遍历
     * @Param:
     * @return:
     * @Author: kukuxiahuni
     * @Date: 2020/1/30
     */
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        inOrder(root.left);
        System.out.println(root.value);
        inOrder(root.right);
    }

    /**
     * @param:
     * @return:
     * @author: kukuxiahuni
     * @create: 2020/2/3 19:57
     * @modify_author: kukuxiahuni
     * @modify_time: 2020/2/3 19:57
     */
    public void inOrderWithIterator(TreeNode root) {

        if (root == null) {
            return;
        }

        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {

            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            System.out.println(cur.value);
            cur = cur.right;

        }

    }

    /**
     * @Description: 后续遍历
     * @Param:
     * @return:
     * @Author: kukuxiahuni
     * @Date: 2020/1/30
     */
    public void postOrder(TreeNode root) {

        if (root == null) {
            return;
        }

        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.value);
    }

    /**
     * @Description: 广度优先搜索, 就是按层次过滤
     * 需要使用队列
     * @Param:
     * @return:
     * @Author: kukuxiahuni
     * @Date: 2020/1/30
     */
    public void bfs(TreeNode root) {

        if (root == null) {
            return;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);

        /**
         * 按照层次进行遍历
         */
        while (!queue.isEmpty()) {
            TreeNode p = queue.poll();
            System.out.println(p.value);
            if (p.left != null) {
                queue.add(p.left);
            }

            if (p.right != null) {
                queue.add(p.right);
            }

        }

    }

    /**
     * @Description: 根据值查找节点
     * @Param:
     * @return:
     * @Author: kukuxiahuni
     * @Date: 2020/1/31
     */
    public final TreeNode<T> find(T value) {
        if (value == null || this.root == null) {
            return null;
        }


        TreeNode<T> p = this.root;

        while (p != null) {

            if (p.value.equals(value)) {
                return p;
            } else {
                int comp = this.compare(p.value, value);
                if (comp < 0) {
                    //右子树
                    p = p.right;
                } else {
                    p = p.left;
                }
            }
        }
        //未找到
        return null;
    }


    /**
     * @Description: 添加树的节点
     * @Param:
     * @return:
     * @Author: kukuxiahuni
     * @Date: 2020/1/25
     */
    public void add(T value) {

        if (value == null) {
            return;
        }

        TreeNode<T> tTreeNode = new TreeNode<>(value, null, null);
        //遍历树,查找节点需要存放的位置
        if (root == null) {
            this.root = tTreeNode;
            return;
        }

        TreeNode<T> p = this.root;

        while (p != null) {
            //1. 如果p.value < value : return -1
            //2. if p.value > value : return 1
            int compare = this.compare(p.value, value);
            //1. 右子树
            if (compare < 0) {
                if (p.right == null) {
                    p.right = tTreeNode;
                    return;
                }
                p = p.right;
            } else {
                if (p.left == null) {
                    p.left = tTreeNode;
                    return;
                }
                p = p.left;
            }
        }

        return;
    }

    /**
     * @Description: 删除指定值的节点
     * @Param:
     * @return:
     * @Author: kukuxiahuni
     * @Date: 2020/1/31
     */
    public final void delete(T value) {

        if (value == null) {
            return;
        }

        TreeNode<T> p = this.root;
        TreeNode<T> pp = null;

        //1. 找到节点位置,包括其父节点位置
        while (p != null && !p.value.equals(value)) {
            pp = p;
            int comp = this.compare(p.value, value);

            if (comp < 0) {
                p = p.right;
            } else {
                p = p.left;
            }
        }

        if (p == null) {
            //没有找到
            return;
        }

        //2. 判定其节点类型,确定删除位置
        /**
         * 1. 待删除的节点左右齐全
         * 2. 找到右子树中的最左子树节点(最小节点)
         * 3. 使用该节点的值,替换待删除节点的值,并删除该节点
         */

        if (p.left != null && p.right != null) {
            TreeNode<T> minP = p.right;
            TreeNode<T> minPP = null;

            while (minP.left != null) {
                minPP = minP;
                minP = minP.left;
            }
            //数据替换
            p.value = minP.value;
            p = minP;
            pp = minPP;
        }

        /**
         * 2. 如果只有一个子树,可能是左子树也可能是右子树
         */
        TreeNode<T> child = null;
        if (p.right != null) {
            child = p.right;
        } else if (p.left != null) {
            child = p.left;
        } else {
            /**
             * 3. 叶子节点的场景
             */
            child = null;
        }

        /**
         * 执行删除操作
         */
        if (pp == null) {
            /**
             * 删除的为根节点
             */
            this.root = child;

        } else if (pp.left == p) {
            pp.left = child;
        } else {
            pp.right = child;
        }
    }

    /**
     * @Description: 树节点
     * @Param:
     * @return:
     * @Author: kukuxiahuni
     * @Date: 2020/1/25
     */
    private final static class TreeNode<T> {

        T value;
        TreeNode<T> left;
        TreeNode<T> right;

        public TreeNode(T value, TreeNode<T> left, TreeNode<T> right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }


    }

    /**
     * @Description: 获取树的深度
     * @Param:
     * @return:
     * @Author: kukuxiahuni
     * @Date: 2020/1/31
     */
    public final int depth(TreeNode root) {

        if (root == null) {
            return 0;
        }

        int left = depth(root.left);
        int right = depth(root.right);

        return Math.max(left, right) + 1;

    }

    /**
     * 比较操作
     * 将当前对象a和指定对象b进行比较.
     * a>b:返回正数;
     * a=b:返回0;
     * a<b:返回负数;
     *
     * @param first
     * @param second
     * @return
     */
    private final int compare(T first, T second) {
        return (this.comparator == null) ? ((Comparable) first).compareTo(second) : this.comparator.compare(first, second);
    }

    public static void main(String[] args) {

        BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();

        int[] array = {86, 8, 88, 9, 97, 72, 90, 26, 20, 28};
        for (int n : array) {
            binarySearchTree.add(n);
        }

        binarySearchTree.preOrder(binarySearchTree.root);

        System.out.println("*******************************************8");
        binarySearchTree.preOrderWithIterator(binarySearchTree.root);
        System.out.println("*******************************************8");
        binarySearchTree.preOrderWithIterator2(binarySearchTree.root);

//        binarySearchTree.inOrder(binarySearchTree.root);
//        System.out.println("*******************************************8");
//        binarySearchTree.inOrderWithIterator(binarySearchTree.root);
//        binarySearchTree.bfs(binarySearchTree.root);

//        System.out.println("*******************************************8");
//        TreeNode<Integer> node = binarySearchTree.find(72);
//        System.out.println(node.value);

//        binarySearchTree.delete(72);

//        System.out.println("*******************************************8");
//        binarySearchTree.bfs(binarySearchTree.root);
//        node = binarySearchTree.find(72);
//        if (node != null) {
//            System.out.println("*******************************************8");
//            System.out.println(node.value);
//        }


//        System.out.println("*******************************************8");
//        System.out.println(binarySearchTree.depth(binarySearchTree.root));

    }
}
